package org.laizili.solution.leetcode;

/**
 * <a href="https://leetcode.cn/problems/flip-string-to-monotone-increasing/">926. 将字符串翻转到单调递增</a>
 */
public class Problem926 {
    private static class Solution {
        public int minFlipsMonoIncr(String s) {
            char[] charArr = s.toCharArray();
            int len = charArr.length;
            int[] prefixOne = new int[len];
            int[] suffixZero = new int[len];
            prefixOne[0] = 0;
            for (int i = 1; i < len; i++) {
                prefixOne[i] = charArr[i - 1] == '1' ? prefixOne[i - 1] + 1 : prefixOne[i - 1];
            }

            for (int j = len - 2; j >= 0; j--) {
                suffixZero[j] = charArr[j + 1] == '0' ? suffixZero[j + 1] + 1 : suffixZero[j + 1];
            }
            int ans = len;
            for (int k = 0; k < len; k++) {
                ans = Math.min(ans, prefixOne[k] + suffixZero[k]);
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        System.err.println(new Solution().minFlipsMonoIncr("1111001110"));
    }
}
